package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/11/5 7:38 下午
 * @see [1218. Longest Arithmetic Subsequence of Given Difference](https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/)
 */
public class LongestArithmeticSubsequenceOfGivenDifference {

    /**
     * 解法一： 暴力解法+备忘录节时
     * @param arr
     * @param difference
     * @return
     */
    public int longestSubsequence(int[] arr, int difference) {
        int len = arr.length, result = Integer.MIN_VALUE, tag;
        Map<Integer, List<Integer>> numToMaxIndex = new HashMap<>(16);
        List<Integer> indexList = new ArrayList<>();
        if (difference == 0) {
            for (int i = 0; i < len; i++) {
                indexList = numToMaxIndex.getOrDefault(arr[i], new ArrayList<>());
                indexList.add(i);
                if (indexList.size() > result) {
                    result = indexList.size();
                }
                numToMaxIndex.put(arr[i], indexList);
            }
            return result;
        }
        for (int i = 0; i < len; i++) {
            indexList = numToMaxIndex.getOrDefault(arr[i], new ArrayList<>());
            indexList.add(i);
            numToMaxIndex.put(arr[i], indexList);
        }
        boolean[] dp = new boolean[len];
        int nextIndex, tagValue, tagIndex;
        boolean flag;
        for (int i = 0; i < len; i++) {
            tag = 1;
            tagValue = arr[i];
            tagIndex = i;
            if (dp[i] == false) {
                while (true) {
                    tagValue += difference;
                    nextIndex = -1;
                    flag = true;
                    indexList = numToMaxIndex.getOrDefault(tagValue, new ArrayList<>());
                    if (indexList.isEmpty()) {
                        break;
                    }
                    for (Integer index : indexList) {
                        if (index > tagIndex && flag) {
                            nextIndex = index;
                            flag = false;
                        }
                        dp[index] = true;

                    }
                    if (nextIndex == -1) {
                        break;
                    }
                    tag++;
                    tagIndex = nextIndex;
                }
                if (tag > result) {
                    result = tag;
                }
            }
        }
        return result;
    }


    /**
     * 解法二：动态规划+备忘录解法 测试用例全部通过，但是提示超时
     * 还有一种优化解法就是利用map代替DP数组
     * @param arr
     * @param difference
     * @return
     */
    public int longestSubsequence2(int[] arr, int difference) {
        int len = arr.length, result = Integer.MIN_VALUE;
        int[] dp = new int[len];
        Set<Integer> usedNum = new HashSet<>(16);
        for (int i = 0; i < len; i++) {
            dp[i] = 1;
            if (usedNum.contains(arr[i] - difference)) {
                for (int j = i-1; j >= 0; j--) {
                    if (arr[j] + difference == arr[i]) {
                        dp[i] = Math.max(dp[i],dp[j]+1);
                        break;
                    }
                }
            }
            if (dp[i] > result) {
                result = dp[i];
            }
            usedNum.add(arr[i]);
        }
        return result;
    }
}
